{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE FunctionalDependencies #-}
{- # LANGUAGE FlexibleInstances # -}
module Leandro where


data Abb a b = Branch a b (Abb a b) (Abb a b) | Leaf
data ListAssoc a b = Node a b (ListAssoc a b) | Empty

minarb :: Abb a b -> Maybe (a,b)
minarb Leaf = Nothing
minarb (Branch ni nd Leaf rd) = Just (ni,nd)
minarb (Branch ni nd ri rd) = minarb ri

class Container c a b |c -> a, c -> b where
   empty :: c

   add :: c -> a -> b -> c

   search :: c -> a -> Maybe b
   del :: c -> a -> c
   toListPair :: c -> [(a,b)]


instance (Ord a) => Container (Abb a b) a b where

   empty = Leaf
   add Leaf x y = Branch x y Leaf Leaf
   add arb@(Branch ni nd ri rd) x y
       |x == ni = arb
       |x > ni = Branch ni nd ri (add rd x y)
       |otherwise = Branch ni nd (add ri x y) rd
   search Leaf x = Nothing
   search (Branch ni nd ri rd) x
       |x == ni = Just nd
       |x > ni = search rd x
       |x < ni = search ri x
   toListPair Leaf = []
   toListPair (Branch ni nd ri rd) = toListPair ri ++ [(ni,nd)] ++ toListPair rd
   del Leaf x = Leaf
   del (Branch ni nd ri rd) x   |x == ni = case minarb rd of
                                           Nothing -> ri
                                           Just (m,n) -> Branch m n ri (del rd m)
                                |x > ni = del rd x
                                |otherwise = del ri x

instance (Ord a) => Container (ListAssoc a b) a b where

   empty = Empty
   add Empty x y = Node x y Empty
   add l@(Node a b lst) x y   |x == a = l
                              |x > a = Node a b (add lst x y)
                              |otherwise = Node x y l

   search Empty x = Nothing
   search (Node a b lst) x    |x == a = Just b
                              |otherwise = search lst x
   del Empty x = Empty
   del (Node a b lst) x       |x == a = lst
                              |otherwise = Node a b (del lst x)
   toListPair Empty = []
   toListPair (Node a b lst) = (a,b):(toListPair lst)